package offer_test_20;

import struct.LinkedNode;

//定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
public class sixteen_ReverList {
	public static void main(String[] args) {
		LinkedNode head = new LinkedNode();
		LinkedNode second = new LinkedNode();
		LinkedNode third = new LinkedNode();
		LinkedNode four = new LinkedNode();
		LinkedNode five = new LinkedNode();
		LinkedNode six = new LinkedNode();
		head.next = second;
		second.next = third;
		third.next = four;
		four.next = five;
		five.next = six;
		head.data = 1;
		second.data = 2;
		third.data = 3;
		four.data = 4;
		five.data = 5;
		six.data = 6;
		LinkedNode rs = reverse(head);
		while (rs != null) {
			System.out.println(rs.data);
			rs = rs.next;
		}
		// if (rs.next != null) {
		// rs=rs.next;
		// }else{rs=null;}
		// }
	}

	// 非递归
	public static LinkedNode reverse(LinkedNode head) {
		LinkedNode pre = null;
		LinkedNode now = head;
		LinkedNode next = null;
		if (head == null) {
			return null;
		}
		if (head.next == null) {
			return head;
		}
		while (now != null) {
			next = now.next;
			now.next = pre;
			pre = now;
			now = next;
		}
		head.next = null;
		head = pre;
		return head;
	}

	// 递归
	public static LinkedNode reverse2(LinkedNode head) {
		if (null == head || null == head.next) {
			return head;
		}
		LinkedNode rs=reverse2(head.next);
		head.next.next=head;
		head.next=null;
		return rs;
	}
}
